package com.rui.study.algorithm.P_通配符匹配;

/**
 * @program: study
 * @description:
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 * 说明:s 可能为空，且只包含从 a-z 的小写字母。
 *     p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
 *
 * @author: Yaowr
 * @create: 2019-01-11 11:00
 **/
public class Solution2回溯法_状态表 {
    public boolean isMatch(String s, String p) {
        state = new int[s.length()][p.length()];
        matches(0, 0, s, p);
        return matched;
    }
    private boolean matched;
    private int[][] state;
    private int count;
    private void matches(int i, int j, String s, String p) {
        count++;
        if (i == s.length() || j == p.length()) {
            if (i == s.length() && j == p.length()) matched = true;
            if (j < p.length() && p.charAt(j) == '*') {
                matches(i, j+1, s, p);      // *匹配0个任意字符
            }
            return;
        }
        if (state[i][j] != 1) {
            state[i][j] = 1;
        } else {
            return;
        }
        if (p.charAt(j) == '*') {
            matches(i, j+1, s, p);      // *匹配0个任意字符
            matches(i+1, j+1, s, p);    // *匹配1个任意字符
            matches(i+1, j, s, p);      // *匹配多个任意字符
        } else if (p.charAt(j) == '?') {
            matches(i+1, j+1, s, p);    // ?匹配1个任意字符
        } else if (s.charAt(i) == p.charAt(j)) {
            matches(i+1, j+1, s, p);
        }
    }


    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Solution2回溯法_状态表 solution = new Solution2回溯法_状态表();
//        boolean result = solution.isMatch("abba", "a*");
        boolean result = solution.isMatch("ababbbabbababababbbabababbbabbababababbbab", "*a*b****ab*****ab*a*b****ab*****ab");
        long end = System.currentTimeMillis();
        System.out.println("是否匹配：" + result + ", 耗时：[" + (end - begin) + "ms], matches() 次数：[" + solution.count + "]");
    }
}
